package com.arron.algorithm.leetcodetop100.贪心;

/**
 *
 * 121. 买卖股票的最佳时机
 */
public class 买卖股票的最佳时机 {


    /**
     * 暴力解法，直接超时
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int maxProfit =0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i+1; j < prices.length; j++) {
                maxProfit = Math.max(maxProfit,prices[j]-prices[i]);
            }
        }
        return maxProfit;
    }


    /**
     * 使用贪心选择最优
     * @param prices
     * @return
     */
    public int maxProfit_plus(int[] prices) {


        int cost = Integer.MAX_VALUE;
        int maxProfit = 0;

        if (prices.length == 1){
            return 0;
        }

        for (int i = 1; i < prices.length; i++) {

            cost = Math.min(cost,prices[i-1]);

            maxProfit = Math.max(maxProfit, prices[i] - cost);
        }
        return maxProfit;
    }


}
